package tests;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;

public class UndirectedGraph {

	private final int 			V;
	private int 				E;
	private ArrayList<Edge>[] 	adjacencyList;
	private boolean[]			visited;
	private int					indexCounter = 0;
	private HashMap<String, Integer>	nameToIndex;
	private String[]			indexToName;
	
	/* Test method. */
	public static void main(String[] args) {
		
	}
	
	public UndirectedGraph(int numVertices, int numEdges){
		this.V 			= numVertices;
		this.E 			= numEdges;
		adjacencyList 	= (ArrayList<Edge>[]) new ArrayList[V];
		visited			= new boolean[V];
		nameToIndex		= new HashMap<String, Integer>();
		indexToName		= new String[V];
		for(int i = 0; i < V; i++){
			adjacencyList[i] = new ArrayList<Edge>();
			visited[i] = false;
		}
	}
	
	public void setVisited(int index){
		visited[index] = true;
	}
	
	public boolean getVisited(int index){
		return visited[index];
	}
	
	public int getSize(){
		return V;
	}
	
	public void addName(String name){
		nameToIndex.put(name, indexCounter);
		indexToName[indexCounter] = name;
		indexCounter++;
	}
	
	public int getVertexIndex(String vertexName){
		return nameToIndex.get(vertexName);
	}
	
	public String getVertexString(int index){
		return indexToName[index];
	}
	
	public Iterator<Edge> getEdgeIterator(int index){
		return adjacencyList[index].iterator();
	}
	
	public void addEdge(String v1, String v2, int weight){
		int  v1Index = nameToIndex.get(v1);
		int  v2Index = nameToIndex.get(v2);
		Edge tmp 	 = new Edge(v1Index, v2Index, weight);
		
		// Don't add duplicates
		if(!adjacencyList[v1Index].contains(tmp)){
			adjacencyList[v1Index].add(tmp);
			if(!adjacencyList[v2Index].contains(tmp)){
				adjacencyList[v2Index].add(tmp);	
			}
		}
		
	}

	public String toString(){
		String out = "VERTICES = " + V;
		out += "\nEDGES = " + E;
		for(int i = 0; i < V; i++){
			out += "\n" + i + ":";
			for(Edge e : adjacencyList[i]){
				out += " " + e;
			}
		}
		return out;
	}
	 
	/* INNER CLASS: Edge. */
	public class Edge implements Comparable<Edge>{
		
		private final int 	 v;
		private final int 	 w;
		private final double weight;
		
		public Edge(int v, int w, double weight){
			this.v 		= v;
			this.w 		= w;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge e) {
			if(e.weight > this.weight)
				return -1;
			else if(e.weight < this.weight)
				return 1;
			else 
				return 0;
		}
		
		public int getV(){
			return v;
		}
		
		public int getW(){
			return w;
		}
		
		public double getWeight(){
			return weight;
		}
		
		public int getOppositeVertex(int n){
			if(v == n)
				return w;
			if(w == n)
				return v;
			else throw new RuntimeException("The given vertex is not a member of this edge.");
		}
		
		public boolean contains(int n){
			if((this.v == n) || (this.w == n))
				return true;
			else
				return false;
		}
		
	    public String toString() {
	        return String.format("%d-%d %.5f", v, w, weight);
	    }
	}
	
	/* INNER CLASS: EdgeComparator. */
	public class EdgeComparator implements Comparator<Edge> {

		@Override
		public int compare(Edge o1, Edge o2) {
			if (o1.getWeight() > o2.getWeight())
				return 1;
			else if (o1.getWeight() < o2.getWeight())
				return -1;
			else
				return 0;
		}

	}
}
